{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Largest 1-Bordered Square"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #dynamic-programming #matrix"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #动态规划 #矩阵"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: largest1BorderedSquare"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #最大的以 1 为边界的正方形"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个由若干 <code>0</code> 和 <code>1</code> 组成的二维网格&nbsp;<code>grid</code>，请你找出边界全部由 <code>1</code> 组成的最大 <strong>正方形</strong> 子网格，并返回该子网格中的元素数量。如果不存在，则返回 <code>0</code>。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>grid = [[1,1,1],[1,0,1],[1,1,1]]\n",
    "<strong>输出：</strong>9\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>grid = [[1,1,0,0]]\n",
    "<strong>输出：</strong>1\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= grid.length &lt;= 100</code></li>\n",
    "\t<li><code>1 &lt;= grid[0].length &lt;= 100</code></li>\n",
    "\t<li><code>grid[i][j]</code> 为&nbsp;<code>0</code>&nbsp;或&nbsp;<code>1</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [largest-1-bordered-square](https://leetcode.cn/problems/largest-1-bordered-square/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [largest-1-bordered-square](https://leetcode.cn/problems/largest-1-bordered-square/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[[1,1,1],[1,0,1],[1,1,1]]', '[[1,1,0,0]]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largest1BorderedSquare(self, grid: List[List[int]]) -> int:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        left = [[0] * (n + 1) for _ in range(m + 1)]\n",
    "        up = [[0] * (n + 1) for _ in range(m + 1)]\n",
    "        maxBorder = 0\n",
    "        for i in range(1, m + 1):\n",
    "            for j in range(1, n + 1):\n",
    "                if grid[i - 1][j - 1]:\n",
    "                    left[i][j] = left[i][j - 1] + 1\n",
    "                    up[i][j] = up[i - 1][j] + 1\n",
    "                    border = min(left[i][j], up[i][j])\n",
    "                    while left[i - border + 1][j] < border or up[i][j - border + 1] < border:\n",
    "                        border -= 1\n",
    "                    maxBorder = max(maxBorder, border)\n",
    "        return maxBorder ** 2\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largest1BorderedSquare(self, grid: List[List[int]]) -> int:\n",
    "        m,n = len(grid), len(grid[0])\n",
    "        dp = [[[0,0] for _ in range(n)] for _ in range(m)] # left,up. include cell itself\n",
    "        # dp\n",
    "        ret = 0 # 记录当前最长边长\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] == 0:\n",
    "                    continue\n",
    "                if j == 0:\n",
    "                    dp[i][j][0] = grid[i][j]\n",
    "                else:\n",
    "                    dp[i][j][0] = dp[i][j-1][0] + 1\n",
    "                if i == 0:\n",
    "                    dp[i][j][1] = grid[i][j]\n",
    "                else:\n",
    "                    dp[i][j][1] = dp[i-1][j][1] + 1\n",
    "                potential_len = min(dp[i][j]) # min(left,up)\n",
    "                for l in range(potential_len,0,-1): # 加速点：反向遍历\n",
    "                    if dp[i-l+1][j][0] >= l and dp[i][j-l+1][1] >= l:\n",
    "                        ret = max(ret, l)\n",
    "                        break # 剪枝， 加速点\n",
    "        return ret**2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "  def largest1BorderedSquare(self, grid: List[List[int]]) -> int:\n",
    "        ans=0\n",
    "        m,n=len(grid),len(grid[0])\n",
    "        def check(x1,y1,x2,y2):\n",
    "            for j in range(y1,y2+1):\n",
    "                if grid[x1][j]!=1:\n",
    "                    return False\n",
    "                if grid[x2][j]!=1:\n",
    "                    return False\n",
    "\n",
    "            for i in range(x1,x2+1):\n",
    "                if grid[i][y1]==0:\n",
    "                    return False\n",
    "                if grid[i][y2]==0:\n",
    "                    return False\n",
    "            return True\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                x,y=i,j\n",
    "                while x<m and y<n:\n",
    "                    if check(i,j,x,y):\n",
    "                        ans=max(ans,x-i+1)\n",
    "                    x+=1\n",
    "                    y+=1\n",
    "        return ans*ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largest1BorderedSquare(self, grid: List[List[int]]) -> int:\n",
    "            rows = len(grid)\n",
    "            colums = len(grid[0])\n",
    "            if rows == 1 or colums == 1:\n",
    "                countZ = 0\n",
    "                if rows == 1:\n",
    "                    for i in range(colums):\n",
    "                        if grid[0][i] == 0:\n",
    "                            countZ += 1\n",
    "                    if countZ == colums:\n",
    "                        return 0\n",
    "                else:\n",
    "                    for i in range(rows):\n",
    "                        if grid[i][0] == 0:\n",
    "                            countZ += 1\n",
    "                    if countZ == rows:\n",
    "                        return 0\n",
    "                return 1\n",
    "            MAXD = [[0 for i in range(colums)] for j in range(rows)]\n",
    "            MAXR = [[0 for i in range(colums)] for j in range(rows)]\n",
    "            MAXU = [[0 for i in range(colums)] for j in range(rows)]\n",
    "            MAXL = [[0 for i in range(colums)] for j in range(rows)]\n",
    "            for i in range(rows):\n",
    "                for j in range(colums):\n",
    "                    if grid[i][j] == 0:\n",
    "                        continue\n",
    "                    elif grid[i][j] == 1:\n",
    "                        MAXL[i][j] = max(1,MAXL[i][j])\n",
    "                        MAXR[i][j] = max(1,MAXR[i][j])\n",
    "                        MAXU[i][j] = max(1,MAXU[i][j])\n",
    "                        MAXD[i][j] = max(1,MAXD[i][j])\n",
    "                    else:\n",
    "                        return 0//非法\n",
    "                    count = 1\n",
    "                    nextX = j+1\n",
    "                    while nextX < colums and grid[i][nextX] == 1:\n",
    "                        count += 1\n",
    "                        if MAXL[i][nextX] < count:\n",
    "                            MAXL[i][nextX] = count\n",
    "                        nextX += 1\n",
    "                    if MAXR[i][j] < count:\n",
    "                        MAXR[i][j] = count\n",
    "                    count = 1\n",
    "                    nextX = i+1\n",
    "                    while nextX < rows and grid[nextX][j] == 1:\n",
    "                        count += 1\n",
    "                        if MAXU[nextX][j] < count:\n",
    "                            MAXU[nextX][j] = count\n",
    "                        nextX += 1\n",
    "                    if MAXD[i][j] < count:\n",
    "                        MAXD[i][j] = count\n",
    "            MAX = 0\n",
    "            MAXDR = [[0 for i in range(colums)] for j in range(rows)]\n",
    "            MAXUL = [[0 for i in range(colums)] for j in range(rows)]\n",
    "            print(\"原矩阵\")\n",
    "            for i in range(rows):\n",
    "                for j in range(colums):\n",
    "                    print(grid[i][j],end = ' ')\n",
    "                print()\n",
    "            print(\"右下矩阵\")\n",
    "            for i in range(rows):\n",
    "                for j in range(colums):\n",
    "                    MAXDR[i][j]=min(MAXD[i][j],MAXR[i][j])\n",
    "                    MAXUL[i][j]=min(MAXU[i][j],MAXL[i][j])\n",
    "            for i in range(rows):\n",
    "                for j in range(colums):\n",
    "                    print(MAXDR[i][j],end = ' ')\n",
    "                print()\n",
    "            print(\"左上矩阵\")\n",
    "            for i in range(rows):\n",
    "                for j in range(colums):\n",
    "                    print(MAXUL[i][j],end = ' ')\n",
    "                print()\n",
    "            for i in range(rows):\n",
    "                for j in range(colums):\n",
    "                    if MAXDR[i][j] > MAX:\n",
    "                        for k in range(MAXDR[i][j],MAX,-1):\n",
    "                            if min(k,MAXDR[i][j], MAXUL[i+k-1][j+k-1]) > MAX and k<= min(MAXDR[i][j], MAXUL[i+k-1][j+k-1]):\n",
    "                                MAX = min(k,MAXDR[i][j], MAXUL[i+k-1][j+k-1])\n",
    "                                print(\"赋值:\",k,MAXDR[i][j], MAXUL[i+k-1][j+k-1],\"坐标为:\",i,\" \",j)\n",
    "            return MAX*MAX\n",
    "  "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largest1BorderedSquare(self, grid: List[List[int]]) -> int:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        left = [[0]*(n+1) for _ in range(m+1)]\n",
    "        up = [[0]*(n+1) for _ in range(m+1)]\n",
    "        ans = 0\n",
    "        for i in range(1, m+1):\n",
    "            for j in range(1, n+1):\n",
    "                if grid[i-1][j-1]:\n",
    "                    left[i][j] = left[i][j-1]+1\n",
    "                    up[i][j] = up[i-1][j]+1\n",
    "                    board = min(left[i][j], up[i][j])\n",
    "                    while board>=1:\n",
    "                        if up[i][j-board+1]>=board and left[i-board+1][j] >= board:\n",
    "                            break\n",
    "                        else:\n",
    "                            board -=1\n",
    "                    ans = max(ans, board)\n",
    "        return ans**2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largest1BorderedSquare(self, grid: List[List[int]]) -> int:\n",
    "        if len(grid) == 0 or len(grid[0]) == 0:\n",
    "            return 0\n",
    "        max = 1\n",
    "        m = len(grid)\n",
    "        n = len(grid[0])\n",
    "        r = 0\n",
    "        u = 0\n",
    "        flag = 0\n",
    "        flag1=0\n",
    "        flag2=0\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] == 0:\n",
    "                    continue\n",
    "                else:\n",
    "                    flag = 1\n",
    "                for k in range(i, m):\n",
    "                    if grid[k][j] == 0:\n",
    "                        break\n",
    "                    else:\n",
    "                        u += 1\n",
    "                for p in range(j, n):\n",
    "                    if grid[i][p] == 0:\n",
    "                        break\n",
    "                    else:\n",
    "                        r += 1\n",
    "                for bianchang in range(max,min(r,u)+1):\n",
    "                    for h in range(i + bianchang - 1, i - 1, -1):\n",
    "                        if grid[h][j + bianchang - 1] == 0:\n",
    "                            break\n",
    "                        else:\n",
    "                            if h==i:\n",
    "                                flag1=1\n",
    "                    for g in range(j + bianchang - 1, j - 1, -1):\n",
    "                        if grid[i + bianchang - 1][g] == 0:\n",
    "                            break\n",
    "                        else:\n",
    "                            if g==j:\n",
    "                                flag2=1\n",
    "                    #print(i,j,bianchang,max)\n",
    "                    if bianchang>max and flag1==1 and flag2==1:\n",
    "                        max = bianchang\n",
    "                    flag1,flag2=0,0\n",
    "                r,u=0,0\n",
    "        if flag == 0:\n",
    "            return 0\n",
    "        return max * max\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largest1BorderedSquare(self, grid: List[List[int]]) -> int:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        left = [[0] * (n + 1) for _ in range(m + 1)]\n",
    "        up = [[0] * (n + 1) for _ in range(m + 1)]\n",
    "        maxBorder = 0\n",
    "        for i in range(1, m + 1):\n",
    "            for j in range(1, n + 1):\n",
    "                if grid[i - 1][j - 1]:\n",
    "                    left[i][j] = left[i][j - 1] + 1\n",
    "                    up[i][j] = up[i - 1][j] + 1\n",
    "                    border = min(left[i][j], up[i][j])\n",
    "                    while left[i - border + 1][j] < border or up[i][j - border + 1] < border:\n",
    "                        border -= 1\n",
    "                    maxBorder = max(maxBorder, border)\n",
    "        return maxBorder ** 2\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largest1BorderedSquare(self, grid: List[List[int]]) -> int:\n",
    "        ans=0\n",
    "        m,n=len(grid),len(grid[0])\n",
    "        def check(x1,y1,x2,y2):\n",
    "            for j in range(y1,y2+1):\n",
    "                if grid[x1][j]!=1:\n",
    "                    return False\n",
    "                if grid[x2][j]!=1:\n",
    "                    return False\n",
    "\n",
    "            for i in range(x1,x2+1):\n",
    "                if grid[i][y1]==0:\n",
    "                    return False\n",
    "                if grid[i][y2]==0:\n",
    "                    return False\n",
    "            return True\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                x,y=i,j\n",
    "                while x<m and y<n:\n",
    "                    if x-i+1>ans and check(i,j,x,y):\n",
    "                        ans=x-i+1\n",
    "                    x+=1\n",
    "                    y+=1\n",
    "        return ans*ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largest1BorderedSquare(self, grid: List[List[int]]) -> int:\n",
    "        m,n = len(grid), len(grid[0])\n",
    "        dp = [[[0,0] for _ in range(n)] for _ in range(m)] # left,up. include cell itself\n",
    "        # dp\n",
    "        ret = 0 # 记录当前最长边长\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] == 0:\n",
    "                    continue\n",
    "                if j == 0:\n",
    "                    dp[i][j][0] = grid[i][j]\n",
    "                else:\n",
    "                    dp[i][j][0] = dp[i][j-1][0] + 1\n",
    "                if i == 0:\n",
    "                    dp[i][j][1] = grid[i][j]\n",
    "                else:\n",
    "                    dp[i][j][1] = dp[i-1][j][1] + 1\n",
    "                potential_len = min(dp[i][j]) # min(left,up)\n",
    "                for l in range(potential_len,0,-1): # 加速点：反向遍历\n",
    "                    if dp[i-l+1][j][0] >= l and dp[i][j-l+1][1] >= l:\n",
    "                        ret = max(ret, l)\n",
    "                        break # 剪枝， 加速点\n",
    "        print(dp)\n",
    "        return ret**2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def largest1BorderedSquare(self, grid):\n",
    "        \"\"\"\n",
    "        :type grid: List[List[int]]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        largest_edge = 0\n",
    "        w, h = len(grid), len(grid[0])\n",
    "        def dfs(i, j, largest_edge):\n",
    "            max_d = 0\n",
    "            while i + max_d < w and j + max_d < h and grid[i+max_d][j] == 1 and grid[i][j+max_d] == 1:\n",
    "                max_d += 1\n",
    "            while max_d > 0 and max_d > largest_edge:\n",
    "                is_all_one = True\n",
    "                k = 1\n",
    "                while is_all_one and k < max_d:\n",
    "                    if grid[i+max_d-1][j+k] == 1 and grid[i+k][j+max_d-1] == 1:\n",
    "                        k += 1\n",
    "                    else:\n",
    "                        is_all_one = False\n",
    "                if is_all_one:\n",
    "                    largest_edge = max_d\n",
    "                else:\n",
    "                    max_d -= 1\n",
    "            return largest_edge\n",
    "        for i in range(w):\n",
    "            for j in range(h):\n",
    "                largest_edge = dfs(i, j, largest_edge)\n",
    "        return largest_edge * largest_edge"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largest1BorderedSquare(self, grid: List[List[int]]) -> int:\n",
    "        r,c=len(grid),len(grid[0])\n",
    "        right_to_left=[[0]*(c+1) for _ in range(r+1)]\n",
    "        bottom_to_top=[[0]*(c+1) for _ in range(r+1)]\n",
    "        for i in range(1,r+1):\n",
    "            for j in range(1,c+1):\n",
    "                right_to_left[i][j]=right_to_left[i][j-1]+grid[i-1][j-1]\n",
    "        for j in range(1,c+1):\n",
    "            for i in range(1,r+1):\n",
    "                bottom_to_top[i][j]=bottom_to_top[i-1][j]+grid[i-1][j-1]\n",
    "        max_len=grid[0][0]\n",
    "        \n",
    "        for i in range(r+1):\n",
    "            for j in range(c+1):\n",
    "                for k in range(max(1,max_len),min(i,j)+1):\n",
    "                    br,tr,lc,rc=((i,j),(i,j-k)),((i-k+1,j),(i-k+1,j-k)),((i,j-k+1),(i-k,j-k+1)),((i,j),(i-k,j))\n",
    "                    valid=True\n",
    "                    for (x1,y1),(x2,y2) in [br,tr]:\n",
    "                        if right_to_left[x1][y1]-right_to_left[x2][y2]!=k:\n",
    "                            valid=False\n",
    "                            break\n",
    "                    for (x1,y1),(x2,y2) in [lc,rc]:\n",
    "                        if bottom_to_top[x1][y1]-bottom_to_top[x2][y2]!=k:\n",
    "                            valid=False\n",
    "                            break\n",
    "                    if valid:\n",
    "                        max_len=max(max_len,k)\n",
    "        return max_len**2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largest1BorderedSquare(self, grid: List[List[int]]) -> int:\n",
    "        m,n = len(grid),len(grid[0])\n",
    "        rs = [list(accumulate(row,initial = 0)) for row in grid]\n",
    "        cs = [list(accumulate(col,initial = 0)) for col in zip(*grid)]\n",
    "        for d in range(min(m,n),0,-1):\n",
    "            for i in range(m - d + 1):\n",
    "                for j in range(n - d + 1):\n",
    "                    if rs[i][j + d] - rs[i][j] == d and \\\n",
    "                    rs[i+d-1][j+d] - rs[i+d-1][j] == d and \\\n",
    "                    cs[j][i+d] - cs[j][i] == d and \\\n",
    "                    cs[j+d-1][i+d] - cs[j+d-1][i] == d:\n",
    "                        return d*d\n",
    "        return 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largest1BorderedSquare(self, grid: List[List[int]]) -> int:\n",
    "        max_b = 0\n",
    "        c_l = len(grid[0])\n",
    "        r_l = len(grid)\n",
    "        right = [[0]*(c_l + 1) for x in range(r_l + 1)]\n",
    "        down = [[0]*(c_l + 1) for x in range(r_l + 1)]\n",
    "        print(right)\n",
    "        print(down)\n",
    "        for r in range(r_l-1, -1, -1):\n",
    "            for c in range(c_l-1, -1, -1):\n",
    "                if grid[r][c] == 1:\n",
    "                    right[r][c] =  right[r][c+1] + 1\n",
    "                    down[r][c] =  down[r+1][c] + 1\n",
    "                    border = min(right[r][c], down[r][c])\n",
    "                    while right[r + border - 1][c] < border or down[r][c + border -1] < border:\n",
    "                        border -= 1\n",
    "                    max_b = max(max_b, border)\n",
    "        return max_b ** 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largest1BorderedSquare(self, grid: list[list[int]]) -> int:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        left = [[0] * (n + 1) for _ in range(m + 1)]\n",
    "        up = [[0] * (n + 1) for _ in range(m + 1)]\n",
    "        maxBorder = 0\n",
    "        for i in range(1, m + 1):\n",
    "            for j in range(1, n + 1):\n",
    "                if grid[i - 1][j - 1] == 1:\n",
    "                    left[i][j] = left[i][j - 1] + 1\n",
    "                    up[i][j] = up[i - 1][j] + 1\n",
    "                    borderLen = min(left[i][j], up[i][j])\n",
    "                    while (\n",
    "                        left[i - borderLen + 1][j] < borderLen\n",
    "                        or up[i][j - borderLen + 1] < borderLen\n",
    "                    ):\n",
    "                        borderLen -= 1\n",
    "                    maxBorder = max(maxBorder, borderLen)\n",
    "        return maxBorder**2\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largest1BorderedSquare(self, grid: List[List[int]]) -> int:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        left = [[0] * (n+1) for _ in range(m+1)]\n",
    "        up = [[0] * (n+1) for _ in range(m+1)]\n",
    "        # up = left[:]\n",
    "        maxBoarder = 0\n",
    "        for i in range(1, m+1):\n",
    "            for j in range(1, n+1):\n",
    "                if grid[i-1][j-1]:\n",
    "                    left[i][j] = left[i][j-1] + 1\n",
    "                    up[i][j] = up[i-1][j] + 1\n",
    "                    border = min(left[i][j], up[i][j])\n",
    "                    while (left[i-border+1][j] < border or up[i][j-border+1] < border):\n",
    "                        border -= 1\n",
    "                    maxBoarder = max(maxBoarder, border)\n",
    "        \n",
    "        return maxBoarder ** 2\n",
    "                    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largest1BorderedSquare(self, grid: List[List[int]]) -> int:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        rs = [list(accumulate(row, initial=0)) for row in grid]  # 每行的前缀和\n",
    "        cs = [list(accumulate(col, initial=0)) for col in zip(*grid)]  # 每列的前缀和\n",
    "        for d in range(min(m, n), 0, -1):  # 从大到小枚举正方形边长 d\n",
    "            for i in range(m - d + 1):\n",
    "                for j in range(n - d + 1):  # 枚举正方形左上角坐标 (i,j)\n",
    "                    # 上 左 下 右 四条边 1 的个数均为 d\n",
    "                    if rs[i][j + d] - rs[i][j] == d and \\\n",
    "                       cs[j][i + d] - cs[j][i] == d and \\\n",
    "                       rs[i + d - 1][j + d] - rs[i + d - 1][j] == d and \\\n",
    "                       cs[j + d - 1][i + d] - cs[j + d - 1][i] == d:\n",
    "                        return d * d\n",
    "        return 0\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largest1BorderedSquare(self, grid: List[List[int]]) -> int:\n",
    "        m,n = len(grid),len(grid[0])\n",
    "        rs = [list(accumulate(row,initial = 0)) for row in grid]\n",
    "        cs = [list(accumulate(col,initial = 0)) for col in zip(*grid)]\n",
    "        for d in range(min(m,n),0,-1):\n",
    "            for i in range(m - d + 1):\n",
    "                for j in range(n - d + 1):\n",
    "                    if rs[i][j+d] - rs[i][j] == d and \\\n",
    "                    cs[j][i+d] - cs[j][i] == d and \\\n",
    "                    rs[i+d-1][j+d] - rs[i+d-1][j] == d and \\\n",
    "                    cs[j+d-1][i+d] - cs[j+d-1][i] == d:\n",
    "                        return d * d\n",
    "        return 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largest1BorderedSquare(self, grid):\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        left = [[0] * (n + 1) for _ in range(m + 1)]\n",
    "        up = [[0] * (n + 1) for _ in range(m + 1)]\n",
    "        maxBorder = 0\n",
    "        for i in range(1, m + 1):\n",
    "            for j in range(1, n + 1):\n",
    "                if grid[i - 1][j - 1]:\n",
    "                    left[i][j] = left[i][j - 1] + 1\n",
    "                    up[i][j] = up[i - 1][j] + 1\n",
    "                    border = min(left[i][j], up[i][j])\n",
    "                    while left[i - border + 1][j] < border or up[i][j - border + 1] < border:\n",
    "                        border -= 1\n",
    "                    maxBorder = max(maxBorder, border)\n",
    "        return maxBorder ** 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largest1BorderedSquare(self, grid: List[List[int]]) -> int:\n",
    "        n = len(grid)\n",
    "        m = len(grid[0])\n",
    "        top = [[0 for _ in range(m)] for _ in range(n)]\n",
    "        left = [[0 for _ in range(m)] for _ in range(n)]\n",
    "        for i in range(n):\n",
    "            for j in range(m):\n",
    "                top[i][j] = grid[i][j]\n",
    "                left[i][j] = grid[i][j]\n",
    "                if i and grid[i][j]:\n",
    "                    top[i][j] += top[i-1][j]\n",
    "                if j and grid[i][j]:\n",
    "                    left[i][j] += left[i][j-1]\n",
    "        ans = 0\n",
    "        # print(left, top)\n",
    "        for i in range(n):\n",
    "            for j in range(m):\n",
    "                for k in range(1, min(i,j)+2):\n",
    "                    width = min(top[i][j], left[i][j])\n",
    "                    height = min(top[i][j-k+1], left[i-k+1][j])\n",
    "                    if min(width, height) >= k:\n",
    "                        # print(i,j,width,height,k)\n",
    "                        ans = max(ans, k*k)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largest1BorderedSquare(self, grid: List[List[int]]) -> int:\n",
    "        # 维护右侧连续1和下方连续1数量\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        right = [[0] * n for _ in range(m)]\n",
    "        down = [[0] * n for _ in range(m)]\n",
    "        for r in range(m-1, -1, -1):\n",
    "            for c in range(n-1, -1, -1):\n",
    "                if grid[r][c] == 1:\n",
    "                    right[r][c] = 1 if c == n - 1 else right[r][c + 1] + 1\n",
    "                    down[r][c] = 1 if r == m - 1 else down[r+1][c] + 1\n",
    "        print(f\"right:{right}\")\n",
    "        print(f\"down:{down}\")\n",
    "        for k in range(min(m, n), 0, -1):\n",
    "            for r in range(m-k+1):\n",
    "                for c in range(n-k+1):\n",
    "                    # if grid[r][c] == 0:\n",
    "                    #     continue\n",
    "                    # if r + k - 1 >= m or c + k - 1 >= n:\n",
    "                    #     continue\n",
    "                    uLens = right[r][c]\n",
    "                    dLens = right[r+k-1][c]\n",
    "                    lLens = down[r][c]\n",
    "                    rLens = down[r][c+k-1]\n",
    "                    if uLens >= k and dLens >= k and lLens >= k and rLens >= k:\n",
    "                        return k**2\n",
    "        return 0\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largest1BorderedSquare(self, grid: List[List[int]]) -> int:\n",
    "        r = len(grid)\n",
    "        c = len(grid[0])\n",
    "        flag0 = 0\n",
    "        for i in range(r):\n",
    "            for j in range(c):\n",
    "                if grid[i][j] == 1 :\n",
    "                    flag0 = 1\n",
    "                    break\n",
    "        if flag0 == 0:\n",
    "            return 0\n",
    "        \n",
    "        max_length = 1\n",
    "        for length in range(max_length,min(r,c)+1):\n",
    "            # print(\"length\",length)\n",
    "            flag_len = False\n",
    "            for i in range(r-length+1):\n",
    "                if flag_len is True:\n",
    "                    break\n",
    "                for j in range(c-length+1):\n",
    "                    if flag_len is True:\n",
    "                        break\n",
    "                    # print(\"i,j\",i,j)\n",
    "                    if grid[i][j] ==1:\n",
    "                        flag = False\n",
    "                        for jj in range(j,j+length):\n",
    "                            if grid[i][jj]==0:\n",
    "                                # print(\"break1\")\n",
    "                                flag=True\n",
    "                                break\n",
    "                            if grid[i+length-1][jj]==0:\n",
    "                                flag=True\n",
    "                                # print(\"break2\")\n",
    "                                break\n",
    "                        if flag is True:\n",
    "                            continue\n",
    "                        for ii in range(i+1,i+length-1):\n",
    "                            if grid[ii][j]==0:\n",
    "                                # print(\"break3\")\n",
    "                                flag=True\n",
    "                                break\n",
    "                            if grid[ii][j+length-1]==0:\n",
    "                                flag=True\n",
    "                                # print(\"break4\")\n",
    "                                break\n",
    "                        if flag is True:\n",
    "                            continue\n",
    "                        else:\n",
    "                            max_length = length\n",
    "                            flag_len = True\n",
    "        return max_length*max_length"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largest1BorderedSquare(self, grid: List[List[int]]) -> int:\n",
    "        r,c=len(grid),len(grid[0])\n",
    "        right_to_left=[[0]*(c+1) for _ in range(r+1)]\n",
    "        bottom_to_top=[[0]*(c+1) for _ in range(r+1)]\n",
    "        for i in range(1,r+1):\n",
    "            for j in range(1,c+1):\n",
    "                right_to_left[i][j]=right_to_left[i][j-1]+grid[i-1][j-1]\n",
    "        for j in range(1,c+1):\n",
    "            for i in range(1,r+1):\n",
    "                bottom_to_top[i][j]=bottom_to_top[i-1][j]+grid[i-1][j-1]\n",
    "        # print('right_to_left')\n",
    "        # for i in range(0,r+1):\n",
    "        #     print(right_to_left[i])\n",
    "        # print('bottom_to_top')\n",
    "        # for i in range(0,r+1):\n",
    "        #     print(bottom_to_top[i])\n",
    "        max_len=grid[0][0]\n",
    "        \n",
    "        for i in range(r+1):\n",
    "            for j in range(c+1):\n",
    "                for k in range(max(1,max_len),min(i,j)+1):\n",
    "                    br,tr,lc,rc=((i,j),(i,j-k)),((i-k+1,j),(i-k+1,j-k)),((i,j-k+1),(i-k,j-k+1)),((i,j),(i-k,j))\n",
    "                    #print('ijk',i,j,k)\n",
    "                    #print(br,tr,lc,rc)\n",
    "                    valid=True\n",
    "                    for (x1,y1),(x2,y2) in [br,tr]:\n",
    "                        #print(right_to_left[x1][y1],right_to_left[x2][y2])\n",
    "                        if right_to_left[x1][y1]-right_to_left[x2][y2]!=k:\n",
    "                            valid=False\n",
    "                            break\n",
    "                    for (x1,y1),(x2,y2) in [lc,rc]:\n",
    "                        #print(bottom_to_top[x1][y1],bottom_to_top[x2][y2])\n",
    "                        if bottom_to_top[x1][y1]-bottom_to_top[x2][y2]!=k:\n",
    "                            valid=False\n",
    "                            break\n",
    "                    if valid:\n",
    "                        max_len=max(max_len,k)\n",
    "        return max_len**2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largest1BorderedSquare(self, grid: List[List[int]]) -> int:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        left, up = [[0] * n for _ in range(m)], [[0] * n for _ in range(m)]\n",
    "        ret = 0\n",
    "\n",
    "        if grid[0][0] == 1:\n",
    "            left[0][0], up[0][0], ret = 1, 1, 1\n",
    "        for i in range(1, m):\n",
    "            if grid[i][0] == 1:\n",
    "                left[i][0] = 1\n",
    "                up[i][0] = up[i - 1][0] + 1\n",
    "                ret = 1\n",
    "        for j in range(1, n):\n",
    "            if grid[0][j] == 1:\n",
    "                left[0][j] = left[0][j - 1] + 1\n",
    "                up[0][j] = 1\n",
    "                ret = 1\n",
    "        \n",
    "        for i in range(1, m):\n",
    "            for j in range(1, n):\n",
    "                if grid[i][j] == 0:\n",
    "                    continue\n",
    "                left[i][j] = 1 + left[i][j - 1]\n",
    "                up[i][j] = 1 + up[i - 1][j]\n",
    "                max_l = min(left[i][j], up[i][j])\n",
    "                for l in range(1, max_l + 1):\n",
    "                    if up[i][j-l+1] >= l and left[i-l+1][j] >= l:\n",
    "                        ret = max(ret, l)\n",
    "\n",
    "        return ret ** 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largest1BorderedSquare(self, grid: List[List[int]]) -> int:\n",
    "        m, n = len(grid),len(grid[0])\n",
    "        left = [[0] * (n+1) for _ in range(m+1)]\n",
    "        up = [[0] * (n+1) for _ in range(m+1)]\n",
    "        max_border = 0\n",
    "        for i in range(1, m+1):\n",
    "            for j in range(1, n+1):\n",
    "                if grid[i-1][j-1] == 1:\n",
    "                    left[i][j] = left[i][j-1]+1\n",
    "                    up[i][j] = up[i-1][j]+1\n",
    "                    border = min(left[i][j], up[i][j])\n",
    "                    for b in range(border, 0, -1):\n",
    "                        if up[i][j-b+1] >= b and left[i-b+1][j] >= b:\n",
    "                            max_border = max(max_border, b)\n",
    "                            break\n",
    "        return max_border*max_border\n",
    "                    \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largest1BorderedSquare(self, grid: List[List[int]]) -> int:\n",
    "        # m,n = len(grid),len(grid[0])\n",
    "        # srow = [list(itertools.accumulate(row,initial=0)) for row in grid]\n",
    "        # scol = [list(itertools.accumulate(col,initial=0)) for col in zip(*grid)]\n",
    "\n",
    "        # for d in range(min(m,n),0,-1):\n",
    "        #     for i in range(m-d+1):\n",
    "        #         for j in range(n-d+1):\n",
    "        #             if srow[i][j+d]-srow[i][j]==d and srow[i+d-1][j+d]-srow[i+d-1][j]==d and scol[j][i+d]-scol[j][i]==d and scol[j+d-1][i+d]-scol[j+d-1][i]==d:\n",
    "        #                 return d*d\n",
    "        # return 0\n",
    "        \n",
    "        m, n = len(grid), len(grid[0])\n",
    "        rs = [list(accumulate(row, initial=0)) for row in grid]  # 每行的前缀和\n",
    "        cs = [list(accumulate(col, initial=0)) for col in zip(*grid)]  # 每列的前缀和\n",
    "        for d in range(min(m, n), 0, -1):  # 从大到小枚举正方形边长 d\n",
    "            for i in range(m - d + 1):\n",
    "                for j in range(n - d + 1):  # 枚举正方形左上角坐标 (i,j)\n",
    "                    # 上 左 下 右 四条边 1 的个数均为 d\n",
    "                    if rs[i][j + d] - rs[i][j] == d and \\\n",
    "                       cs[j][i + d] - cs[j][i] == d and \\\n",
    "                       rs[i + d - 1][j + d] - rs[i + d - 1][j] == d and \\\n",
    "                       cs[j + d - 1][i + d] - cs[j + d - 1][i] == d:\n",
    "                        return d * d\n",
    "        return 0\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largest1BorderedSquare(self, grid: List[List[int]]) -> int:\n",
    "        m,n = len(grid),len(grid[0])\n",
    "        # line_s = [[0]*(n + 1) for _ in range(m)]\n",
    "        # col_s  = [[0]*(m + 1) for _ in range(n)]\n",
    "\n",
    "        # for i,row in enumerate(grid):\n",
    "        #     for j,x in enumerate(row):\n",
    "        #         line_s[i][j + 1] = line_s[i][j] + x\n",
    "        # for j,col in enumerate(zip(*grid)):\n",
    "        #     for i,x in enumerate(col):\n",
    "        #         col_s[j][i + 1] = col_s[j][i] + x\n",
    "        line_s = [[0] + list(accumulate(row)) for row in grid]\n",
    "        col_s = [[0] + list(accumulate(col)) for col in zip(*grid)]\n",
    "        ans = 0\n",
    "        # 枚举左上角\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] == 0:\n",
    "                    continue\n",
    "                # 枚举边长\n",
    "                for L in range(min(n - j,m - i),0,-1):\n",
    "                    up = line_s[i][j + L] - line_s[i][j]\n",
    "                    down = line_s[i + L - 1][j + L] - line_s[i + L - 1][j]\n",
    "                    left = col_s[j][i + L] - col_s[j][i]\n",
    "                    right = col_s[j + L - 1][i + L] - col_s[j + L - 1][i]\n",
    "                    if up == down == left == right == L:\n",
    "                        ans = max(ans,L*L)\n",
    "                        break # L从大到小枚举，找到就可以停了\n",
    "        return ans "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largest1BorderedSquare(self, grid: List[List[int]]) -> int:\n",
    "        grid_sum = [[0 for i in range(len(grid[0])+1)]for j in range(len(grid)+1)]\n",
    "        ans = 0\n",
    "        for i in range(1, len(grid_sum)):\n",
    "            for j in range(1, len(grid_sum[0])):\n",
    "                grid_sum[i][j] = grid_sum[i-1][j]+grid_sum[i][j-1]-grid_sum[i-1][j-1]+grid[i-1][j-1]\n",
    "        # print(grid_sum)\n",
    "        for i in range(1, len(grid_sum)):\n",
    "            for j in range(1, len(grid_sum[0])):\n",
    "                edge = min(len(grid_sum)-i, len(grid_sum[0])-j)\n",
    "                for k in range(max(0, ans), edge):\n",
    "                    if grid_sum[i+k][j+k]==0:\n",
    "                        break\n",
    "                    sum1 = grid_sum[i+k][j+k]-grid_sum[i+k][j-1]-grid_sum[i-1][j+k]+grid_sum[i-1][j-1]\n",
    "                    sum2 = grid_sum[i+k-1][j+k-1]-grid_sum[i+k-1][j]-grid_sum[i][j+k-1]+grid_sum[i][j]\n",
    "                    # print('i', i, 'j', j, 'k', k, 'sum1', sum1,'sum2', sum2)\n",
    "                    # 1 4 8 12 16 \n",
    "                    if sum1-sum2==k*4 and sum1!=0:\n",
    "                        ans = max(1+k, ans)\n",
    "        return ans**2\n",
    "\n",
    "\n",
    "        \n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largest1BorderedSquare(self, grid: List[List[int]]) -> int:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        left = [[0] * (n + 1) for _ in range(m + 1)]\n",
    "        up = [[0] * (n + 1) for _ in range(m + 1)]\n",
    "        res = 0\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] == 1:\n",
    "                    left[i+1][j+1] = left[i+1][j] + 1\n",
    "                    up[i+1][j+1] = up[i][j+1] + 1\n",
    "                    l = min(left[i+1][j+1], up[i+1][j+1])\n",
    "                    while left[i-l+2][j+1] < l or up[i+1][j-l+2] < l:\n",
    "                        l -= 1\n",
    "                    res = max(res, l)\n",
    "        return res**2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largest1BorderedSquare(self, grid: List[List[int]]) -> int:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        left = [[0] * (n + 1) for _ in range(m + 1)]\n",
    "        up = [[0] * (n + 1) for _ in range(m + 1)]\n",
    "        maxBorder = 0\n",
    "        for i in range(1, m + 1):\n",
    "            for j in range(1, n + 1):\n",
    "                if grid[i-1][j-1]:\n",
    "                    left[i][j] = left[i][j-1] + 1\n",
    "                    up[i][j] = up[i-1][j] + 1\n",
    "                    border = min(left[i][j], up[i][j])\n",
    "                    while left[i - border + 1][j] < border or up[i][j-border+1] < border:\n",
    "                        border -= 1\n",
    "                    maxBorder = max(maxBorder, border)\n",
    "        return maxBorder ** 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largest1BorderedSquare(self, grid: List[List[int]]) -> int:\n",
    "        m,n = len(grid),len(grid[0])\n",
    "        rs = [list(accumulate(row,initial = 0)) for row in grid]\n",
    "        cs = [list(accumulate(col,initial = 0)) for col in zip(*grid)]\n",
    "        for d in range(min(m,n),0,-1):\n",
    "            for i in range(m - d + 1):\n",
    "                for j in range(n - d + 1):\n",
    "                    if rs[i][j+d] - rs[i][j] == d and \\\n",
    "                    cs[j][i+d] - cs[j][i] == d and \\\n",
    "                    rs[i+d-1][j+d] - rs[i+d-1][j] == d and \\\n",
    "                    cs[j+d-1][i+d] - cs[j+d-1][i] == d:\n",
    "                        return d * d\n",
    "        return 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largest1BorderedSquare(self, grid: List[List[int]]) -> int:\n",
    "        rows = len(grid)\n",
    "        cols = len(grid[0])\n",
    "        up = [[0]*(cols+1) for _ in range(rows+1)]\n",
    "        left = [[0]*(cols+1) for _ in range(rows+1)]\n",
    "        l = 0\n",
    "        ans = 0\n",
    "        for i in range(1, rows+1):\n",
    "            for j in range(1, cols+1):\n",
    "                if grid[i-1][j-1]:\n",
    "                    left[i][j] = left[i][j-1]+1\n",
    "                    up[i][j] = up[i-1][j]+1\n",
    "                    l = min(left[i][j], up[i][j])\n",
    "                    \n",
    "                    # 进行四周检查\n",
    "                    while left[i-l+1][j]<l or up[i][j-l+1]<l:\n",
    "                       l-=1\n",
    "                    ans = max(ans, l)\n",
    "\n",
    "        return ans*ans\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largest1BorderedSquare(self, grid: List[List[int]]) -> int:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        rs = [list(accumulate(row, initial=0)) for row in grid]  # 每行的前缀和\n",
    "        cs = [list(accumulate(col, initial=0)) for col in zip(*grid)]  # 每列的前缀和\n",
    "        for d in range(min(m, n), 0, -1):  # 从大到小枚举正方形边长 d\n",
    "            for i in range(m - d + 1):\n",
    "                for j in range(n - d + 1):  # 枚举正方形左上角坐标 (i,j)\n",
    "                    # 上 左 下 右 四条边 1 的个数均为 d\n",
    "                    if rs[i][j + d] - rs[i][j] == d and \\\n",
    "                       cs[j][i + d] - cs[j][i] == d and \\\n",
    "                       rs[i + d - 1][j + d] - rs[i + d - 1][j] == d and \\\n",
    "                       cs[j + d - 1][i + d] - cs[j + d - 1][i] == d:\n",
    "                        return d * d\n",
    "        return 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "class Solution:\n",
    "    def largest1BorderedSquare(self, grid: List[List[int]]) -> int:\n",
    "        if not grid or not grid[0]:\n",
    "            return 0\n",
    "        \n",
    "        m, n = len(grid), len(grid[0])\n",
    "        hor = [[0] * n for _ in range(m)]\n",
    "        ver = [[0] * n for _ in range(m)]\n",
    "        \n",
    "        # Step 1: Fill in the hor and ver arrays\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] == 1:\n",
    "                    hor[i][j] = hor[i][j-1] + 1 if j > 0 else 1\n",
    "                    ver[i][j] = ver[i-1][j] + 1 if i > 0 else 1\n",
    "        \n",
    "        # Step 2: Check for the largest square with border all ones\n",
    "        max_side = 0\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                small = min(hor[i][j], ver[i][j])\n",
    "                while small > max_side:\n",
    "                    if hor[i-small+1][j] >= small and ver[i][j-small+1] >= small:\n",
    "                        max_side = small\n",
    "                    small -= 1\n",
    "        \n",
    "        return max_side * max_side\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largest1BorderedSquare(self, grid: List[List[int]]) -> int:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        rs = [list(accumulate(row, initial=0)) for row in grid]  # 每行的前缀和\n",
    "        cs = [list(accumulate(col, initial=0)) for col in zip(*grid)]  # 每列的前缀和\n",
    "        for d in range(min(m,n),0,-1):\n",
    "            for i in range(m - d + 1):\n",
    "                for j in range(n - d +1):\n",
    "                    if rs[i][j+d] - rs[i][j] == d and rs[i+d-1][j+d] - rs[i+d-1][j] ==d and cs[j][i+d] - cs[j][i] == d and cs[j+d-1][i+d] - cs[j+d-1][i] == d:\n",
    "                        return d*d\n",
    "        return 0\n",
    "\n",
    "\n",
    "                    \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largest1BorderedSquare(self, grid: List[List[int]]) -> int:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        rs = [list(accumulate(row, initial=0)) for row in grid]  # 每行的前缀和\n",
    "        cs = [list(accumulate(col, initial=0)) for col in zip(*grid)]  # 每列的前缀和\n",
    "        for d in range(min(m, n), 0, -1):  # 从大到小枚举正方形边长 d\n",
    "            for i in range(m - d + 1):\n",
    "                for j in range(n - d + 1):  # 枚举正方形左上角坐标 (i,j)\n",
    "                    # 上 左 下 右 四条边 1 的个数均为 d\n",
    "                    if rs[i][j + d] - rs[i][j] == d and \\\n",
    "                       cs[j][i + d] - cs[j][i] == d and \\\n",
    "                       rs[i + d - 1][j + d] - rs[i + d - 1][j] == d and \\\n",
    "                       cs[j + d - 1][i + d] - cs[j + d - 1][i] == d:\n",
    "                        return d * d\n",
    "        return 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largest1BorderedSquare(self, grid: List[List[int]]) -> int:\n",
    "        rows = [[0]*len(grid[0]) for _ in range(len(grid))]\n",
    "        columns = [[0]*len(grid[0]) for _ in range(len(grid))]\n",
    "        m,n = len(grid),len(grid[0])\n",
    "        res = 0\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] == 1:\n",
    "                    if i == 0:\n",
    "                        rows[i][j] = 1\n",
    "                    else:\n",
    "                        rows[i][j] = rows[i-1][j]+1\n",
    "                    if j == 0:\n",
    "                        columns[i][j] = 1\n",
    "                    else:\n",
    "                        columns[i][j] = columns[i][j-1] + 1\n",
    "        print(columns,rows)\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                max_sq = min(rows[i][j],columns[i][j])\n",
    "                for k in range(max_sq+1):\n",
    "                    c2,r2 = rows[i][j-k],columns[i-k][j]\n",
    "                    if c2 >= k+1 and r2 >= k+1:\n",
    "                        res = max(res,(k+1)**2)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largest1BorderedSquare(self, grid: List[List[int]]) -> int:\n",
    "        row_prefixes = []\n",
    "        col_prefixes = []\n",
    "        m = len(grid)\n",
    "        n = len(grid[0])\n",
    "        for i in range(m):\n",
    "            row_prefixes.append(list(accumulate(grid[i], initial=0)))\n",
    "        for j in range(n):\n",
    "            col_prefixes.append(list(accumulate([row[j] for row in grid], initial=0)))\n",
    "        print(row_prefixes)\n",
    "        print(col_prefixes)\n",
    "        for k in range(min(n, m), 0, -1):\n",
    "            for i in range(k-1, m):\n",
    "                for j in range(k-1, n):\n",
    "                    # left_up = i-k+1, j-k+1\n",
    "                    # left_low = i, j-k+1\n",
    "                    # right_up = i-k+1, j\n",
    "                    # right_low = i, j\n",
    "                    up_zeros = row_prefixes[i-k+1][j+1] - row_prefixes[i-k+1][j-k+1]\n",
    "                    left_zeros = col_prefixes[j-k+1][i+1] - col_prefixes[j-k+1][i-k+1]\n",
    "                    right_zeros = col_prefixes[j][i+1] - col_prefixes[j][i-k+1]\n",
    "                    low_zeros = row_prefixes[i][j+1] - row_prefixes[i][j-k+1]\n",
    "                    # print(up_zeros, left_zeros, right_zeros, low_zeros)\n",
    "                    if up_zeros == k and left_zeros == k and right_zeros == k and low_zeros == k:\n",
    "                        return k*k\n",
    "        return 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largest1BorderedSquare(self, grid: List[List[int]]) -> int:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        rs = [list(accumulate(row, initial=0)) for row in grid]  # 每行的前缀和\n",
    "        cs = [list(accumulate(col, initial=0)) for col in zip(*grid)]  # 每列的前缀和\n",
    "        for d in range(min(m, n), 0, -1):  # 从大到小枚举正方形边长 d\n",
    "            for i in range(m - d + 1):\n",
    "                for j in range(n - d + 1):  # 枚举正方形左上角坐标 (i,j)\n",
    "                    # 上 左 下 右 四条边 1 的个数均为 d\n",
    "                    if rs[i][j + d] - rs[i][j] == d and \\\n",
    "                       cs[j][i + d] - cs[j][i] == d and \\\n",
    "                       rs[i + d - 1][j + d] - rs[i + d - 1][j] == d and \\\n",
    "                       cs[j + d - 1][i + d] - cs[j + d - 1][i] == d:\n",
    "                        return d * d\n",
    "        return 0\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largest1BorderedSquare(self, grid: List[List[int]]) -> int:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        prefix_sum = [[0] * (n + 1) for _ in range(m + 1)]\n",
    "        ans = 0\n",
    "\n",
    "        # 计算前缀和\n",
    "        for i in range(1, m + 1):\n",
    "            for j in range(1, n + 1):\n",
    "                prefix_sum[i][j] = (\n",
    "                    prefix_sum[i - 1][j]\n",
    "                    + prefix_sum[i][j - 1]\n",
    "                    - prefix_sum[i - 1][j - 1]\n",
    "                    + grid[i - 1][j - 1]\n",
    "                )\n",
    "                if grid[i - 1][j - 1] != 1:\n",
    "                    continue\n",
    "\n",
    "                # 尝试不同的正方形大小\n",
    "                for k in range(1, min(i, j) + 1):\n",
    "                    s1 = (\n",
    "                        prefix_sum[i][j]\n",
    "                        - prefix_sum[i - k][j]\n",
    "                        - prefix_sum[i][j - k]\n",
    "                        + prefix_sum[i - k][j - k]\n",
    "                    )\n",
    "                    s2 = (\n",
    "                        prefix_sum[i - 1][j - 1]\n",
    "                        - prefix_sum[i - k + 1][j - 1]\n",
    "                        - prefix_sum[i - 1][j - k + 1]\n",
    "                        + prefix_sum[i - k + 1][j - k + 1]\n",
    "                    )\n",
    "                    t = k - 2\n",
    "\n",
    "                    # 检查正方形是否有效\n",
    "                    if s1 - s2 == k * k - t * t:\n",
    "                        ans = max(ans, k * k)\n",
    "\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largest1BorderedSquare(self, grid: List[List[int]]) -> int:\n",
    "        s = [[0]*(len(grid[0])+1) for _ in range(len(grid)+1)]\n",
    "        for i in range(1, len(s)):\n",
    "            for j in range(1, len(s[0])):\n",
    "                s[i][j] = s[i-1][j] + s[i][j-1] - s[i-1][j-1] + grid[i-1][j-1]\n",
    "        \n",
    "        if s[len(s)-1][len(s[0])-1] == 0:\n",
    "            return 0\n",
    "        maxnum = 1\n",
    "        for i in range(len(grid)):\n",
    "            for j in range(len(grid[0])):\n",
    "                maxs = min(i, j) + 1\n",
    "                if maxs > maxnum:\n",
    "                    for n in range(maxs, maxnum, -1):\n",
    "                        if self.check(s, i, j, n):\n",
    "                            maxnum = max(maxnum, n)\n",
    "        return maxnum**2\n",
    "\n",
    "    def check(self, s, i, j, n):\n",
    "        s2 = self.sumRegion(s, i-n+1, j-n+1, i, j)\n",
    "        s1 = self.sumRegion(s, i-n+2, j-n+2, i-1, j-1)\n",
    "        if s2 - s1 == 2*n + 2*(n-2):\n",
    "            return True\n",
    "        else:\n",
    "            return False\n",
    "\n",
    "    def sumRegion(self, s, row1, col1, row2, col2):\n",
    "        if col1 > col2 or row1 > row2:\n",
    "            return 0\n",
    "        return s[row2+1][col2+1] - s[row2+1][col1] - s[row1][col2+1] + s[row1][col1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largest1BorderedSquare(self, grid: List[List[int]]) -> int:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        rs = [list(accumulate(row, initial=0)) for row in grid]  # 每行的前缀和\n",
    "        cs = [list(accumulate(col, initial=0)) for col in zip(*grid)]  # 每列的前缀和\n",
    "        print(rs)\n",
    "        for d in range(min(m, n), 0, -1):  # 从大到小枚举正方形边长 d\n",
    "            for i in range(m - d + 1):\n",
    "                for j in range(n - d + 1):  # 枚举正方形左上角坐标 (i,j)\n",
    "                    # 上 左 下 右 四条边 1 的个数均为 d\n",
    "                    if rs[i][j + d] - rs[i][j] == d and \\\n",
    "                       cs[j][i + d] - cs[j][i] == d and \\\n",
    "                       rs[i + d - 1][j + d] - rs[i + d - 1][j] == d and \\\n",
    "                       cs[j + d - 1][i + d] - cs[j + d - 1][i] == d:\n",
    "                        return d * d\n",
    "        return 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largest1BorderedSquare(self, grid: List[List[int]]) -> int:\n",
    "        m,n=len(grid),len(grid[0])\n",
    "        prefix_sum=[[0]*(n+1) for _ in range(m+1)]\n",
    "        ans=0\n",
    "\n",
    "        for i in range(1,m+1):\n",
    "            for j in range(1,n+1):\n",
    "                prefix_sum[i][j]=(\n",
    "                        prefix_sum[i - 1][j]\n",
    "                        + prefix_sum[i][j - 1]\n",
    "                        - prefix_sum[i - 1][j - 1]\n",
    "                        + grid[i - 1][j - 1]\n",
    "                )\n",
    "                if grid[i-1][j-1]!=1:\n",
    "                    continue\n",
    "\n",
    "                for k in range(1,min(i,j)+1):\n",
    "                    s1 = (\n",
    "                            prefix_sum[i][j]\n",
    "                            - prefix_sum[i - k][j]\n",
    "                            - prefix_sum[i][j - k]\n",
    "                            + prefix_sum[i - k][j - k]\n",
    "                    )\n",
    "                    s2 = (\n",
    "                        prefix_sum[i - 1][j - 1]\n",
    "                        - prefix_sum[i - k + 1][j - 1]\n",
    "                        - prefix_sum[i - 1][j - k + 1]\n",
    "                        + prefix_sum[i - k + 1][j - k + 1]\n",
    "                    )\n",
    "                    t = k - 2\n",
    "                    if s1 - s2 == k * k - t * t:\n",
    "                        ans = max(ans, k * k)\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largest1BorderedSquare(self, grid: List[List[int]]) -> int:\n",
    "        s = [[0]*(len(grid[0])+1) for _ in range(len(grid)+1)]\n",
    "        for i in range(1, len(s)):\n",
    "            for j in range(1, len(s[0])):\n",
    "                s[i][j] = s[i-1][j] + s[i][j-1] - s[i-1][j-1] + grid[i-1][j-1]\n",
    "        \n",
    "        maxnum = 0\n",
    "        for i in range(len(grid)):\n",
    "            for j in range(len(grid[0])):\n",
    "                maxs = min(i, j) + 1\n",
    "                if grid[i][j] == 1:\n",
    "                    maxnum = max(maxnum, 1)\n",
    "                for n in range(maxs, 1, -1):\n",
    "                    if self.check(s, i, j, n):\n",
    "                        maxnum = max(maxnum, n**2)\n",
    "        return maxnum\n",
    "\n",
    "    def check(self, s, i, j, n):\n",
    "        s2 = self.sumRegion(s, i-n+1, j-n+1, i, j)\n",
    "        s1 = self.sumRegion(s, i-n+2, j-n+2, i-1, j-1)\n",
    "        if s2 - s1 == 2*n + 2*(n-2):\n",
    "            return True\n",
    "        else:\n",
    "            return False\n",
    "\n",
    "    def sumRegion(self, s, row1, col1, row2, col2):\n",
    "        if col1 > col2 or row1 > row2:\n",
    "            return 0\n",
    "        return s[row2+1][col2+1] - s[row2+1][col1] - s[row1][col2+1] + s[row1][col1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largest1BorderedSquare(self, grid: List[List[int]]) -> int:\n",
    "        def calcOnesInSquare(i, j, borderLen, squareAreas):\n",
    "            if borderLen == 0:\n",
    "                return 0\n",
    "            # 返回以 (i, j) 为右上角的正方形中 1 的数量\n",
    "            i2 = i - borderLen\n",
    "            j2 = j - borderLen\n",
    "            return squareAreas[i+1][j+1]-squareAreas[i+1][j2+1]-squareAreas[i2+1][j+1]+squareAreas[i2+1][j2+1]\n",
    "\n",
    "        def maxAreaOfOneBorder(i, j):\n",
    "            # 返回以 (i, j) 为右上角的最大的边界全为 1 的正方形的面积\n",
    "            borderLen = i + 1 if i < j else j + 1\n",
    "            if borderLen == 1:\n",
    "                return grid[i][j]\n",
    "            while borderLen > 1:\n",
    "                largeOnes = calcOnesInSquare(i, j, borderLen, squareAreas)\n",
    "                smallOnes = calcOnesInSquare(i-1, j-1, borderLen - 2, squareAreas)\n",
    "                if largeOnes - smallOnes == 4 * (borderLen - 1):\n",
    "                    return borderLen ** 2\n",
    "                borderLen -= 1\n",
    "            return grid[i][j]\n",
    "\n",
    "        def buildSquareAreas(grid):\n",
    "            squareAreas = [[0 for _ in range(len(grid[0]) + 1)] for _ in range(len(grid) + 1)]\n",
    "            for i in range(len(grid)):\n",
    "                for j in range(len(grid[0])):\n",
    "                    squareAreas[i+1][j+1] = squareAreas[i][j+1] + squareAreas[i+1][j] + grid[i][j] - squareAreas[i][j]\n",
    "            return squareAreas\n",
    "\n",
    "        squareAreas = buildSquareAreas(grid)\n",
    "        res = 0\n",
    "        for i in range(len(grid)):\n",
    "            for j in range(len(grid[0])):\n",
    "                res = max(res, maxAreaOfOneBorder(i, j))\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largest1BorderedSquare(self, grid: List[List[int]]) -> int:\n",
    "        \n",
    "        if not grid or not grid[0]:\n",
    "            return 0\n",
    "        \n",
    "        r, c = len(grid), len(grid[0])\n",
    "        \n",
    "        rows = [[0] * (c + 1) for _ in range(r)]\n",
    "        \n",
    "        for i in range(r):\n",
    "            for j in range(1, c + 1):\n",
    "                rows[i][j] = rows[i][j - 1] + grid[i][j - 1]\n",
    "        \n",
    "        grid_t = list(zip(*grid))\n",
    "        cols = [[0] * (r + 1) for _ in range(c)]\n",
    "        \n",
    "        \n",
    "        for i in range(c):\n",
    "            for j in range(1, r + 1):\n",
    "                cols[i][j] = cols[i][j - 1] + grid_t[i][j - 1]\n",
    "        \n",
    "        print(rows)\n",
    "        print(cols)\n",
    "        \n",
    "        res = 0\n",
    "        \n",
    "        for i in range(r):\n",
    "            for j in range(c):\n",
    "                for d in range(min(r - i, c - j)):\n",
    "                    if rows[i][j + d + 1] - rows[i][j] == d + 1 and rows[i + d][j + d + 1] - rows[i + d][j] == d + 1 and cols[j][i + d + 1] - cols[j][i] == d + 1 and cols[j + d][i + d + 1] - cols[j + d][i] == d + 1:\n",
    "                        \n",
    "                        res = max(res, d + 1)\n",
    "        \n",
    "        return res * res\n",
    "                \n",
    "        \n",
    "        \n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largest1BorderedSquare(self, grid: List[List[int]]) -> int:\n",
    "        presum = [[0] * (len(grid[0]) + 1) for _ in range(len(grid) + 1)]\n",
    "        for i in range(1, len(grid) + 1):\n",
    "            for j in range(1, len(grid[0]) + 1):\n",
    "                presum[i][j] = presum[i - 1][j] + presum[i][j - 1] - presum[i - 1][j - 1] + grid[i - 1][j - 1] \n",
    "        \n",
    "        def get_row(row, l ,r):\n",
    "            return presum[row + 1][r + 1] - presum[row][r + 1] - presum[row + 1][l] + presum[row][l]\n",
    "        def get_col(col, u, d):\n",
    "            return presum[d + 1][col + 1] - presum[d + 1][col] - presum[u][col + 1] + presum[u][col]\n",
    "        res = 0\n",
    "        for i in range(len(grid)):\n",
    "            for j in range(len(grid[0])):\n",
    "                if grid[i][j] == 1:\n",
    "                    res = max(res, 1)\n",
    "                for k in range(2, min(i, j) + 2):\n",
    "                    left_c = j - k + 1\n",
    "                    up_r = i - k + 1\n",
    "                    if get_row(i, left_c, j) + get_row(up_r, left_c, j) + get_col(j, up_r  + 1, i - 1) + get_col(left_c, up_r + 1, i - 1) == 4 * (k - 1):\n",
    "                        res = max(res, k ** 2)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largest1BorderedSquare(self, grid: List[List[int]]) -> int:\n",
    "        mat = [[(0, 0) for j in range(len(grid[0]) + 1)] for i in range(len(grid) + 1)]\n",
    "        ans = 0\n",
    "        for i in range(1, len(mat)):\n",
    "            for j in range(1, len(mat[0])):\n",
    "                if grid[i - 1][j - 1] == 1:\n",
    "                    mat[i][j] = (mat[i - 1][j][0] + 1, mat[i][j - 1][1] + 1)\n",
    "                    for sq in range(min(mat[i][j]), 0, -1):\n",
    "                        if mat[i][j - sq + 1][0] >= sq and mat[i - sq + 1][j][1] >= sq:\n",
    "                            ans = max(ans, sq * sq)\n",
    "                            break\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largest1BorderedSquare(self, grid: List[List[int]]) -> int:\n",
    "        def pre(grid:List[List[int]]):\n",
    "            m,n=len(grid),len(grid[0])\n",
    "            for i in range(1,m):\n",
    "                grid[i][0]+=grid[i-1][0]\n",
    "            \n",
    "            for i in range(1,n):\n",
    "                grid[0][i]+=grid[0][i-1]\n",
    "            \n",
    "            for i in range(1,m):\n",
    "                for j in range(1,n):\n",
    "                    grid[i][j]+=grid[i-1][j]+grid[i][j-1]-grid[i-1][j-1]\n",
    "            \n",
    "        def sumRegion(grid: List[List[int]], row1: int, col1: int, row2: int, col2: int) -> int:\n",
    "        \n",
    "            lt=0 if (col1==0 or row1==0) else grid[row1-1][col1-1]\n",
    "            l=0 if col1==0 else grid[row2][col1-1]\n",
    "            t=0 if row1==0 else grid[row1-1][col2]\n",
    "\n",
    "            return grid[row2][col2]-l-t+lt\n",
    "\n",
    "        def edge(grid: List[List[int]],row_idx:int,col_idx:int,edge_len:int,row_limit:int,col_limit:int)->bool:\n",
    "            if row_idx+edge_len-1>=row_limit or col_idx+edge_len-1>=col_limit:\n",
    "                return False\n",
    "            \n",
    "            if edge_len<=2:\n",
    "                return sumRegion(grid,row_idx,col_idx,row_idx+edge_len-1,col_idx+edge_len-1)==edge_len**2\n",
    "            ans=sumRegion(grid,row_idx,col_idx,row_idx+edge_len-1,col_idx+edge_len-1)-sumRegion(grid,row_idx+1,col_idx+1,row_idx+edge_len-2,col_idx+edge_len-2)\n",
    "            return ans==4*edge_len-4\n",
    "        \n",
    "\n",
    "        pre(grid)\n",
    "        if grid[-1][-1]==0:\n",
    "            return 0\n",
    "        edge_limit=min(len(grid),len(grid[0]))\n",
    "        for edge_len in range(edge_limit,0,-1):\n",
    "            for i in range(len(grid)):\n",
    "                for j in range(len(grid[0])):\n",
    "                    if edge(grid, i, j, edge_len, len(grid), len(grid[0])):\n",
    "                        return edge_len**2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largest1BorderedSquare(self, grid: List[List[int]]) -> int:\n",
    "\n",
    "        m=len(grid)\n",
    "        n=len(grid[0])\n",
    "        ans=0\n",
    "        #print(m,n)\n",
    "        for x in range(m):\n",
    "            for y in range(n):\n",
    "                if grid[x][y]==1:\n",
    "                    ans=max(ans,1)\n",
    "                    print(ans)\n",
    "                    lmax=min(m-1-x,n-1-y)\n",
    "                  #  print(lmax)\n",
    "                    for l in range(lmax,-1,-1):\n",
    "                        f=0\n",
    "                        x1=x+l\n",
    "                        y1=y+l\n",
    "                       \n",
    "                        if sum(grid[x][y:y1+1])!=l+1 or sum(grid[x1][y:y1+1])!=l+1:\n",
    "                            f=1\n",
    "                        for i in range(x,x1+1):\n",
    "                            if grid[i][y]==0 or grid[i][y1]==0:\n",
    "                                f=1\n",
    "                                break\n",
    "                        if f==0:\n",
    "                            cnt=0\n",
    "                          #  print(1000)\n",
    "                            cnt=(l+1)*(l+1)\n",
    "                            ans=max(ans,cnt)\n",
    "                            break\n",
    "        return ans\n",
    "                    \n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class PreFixSumMatrix:\n",
    "    def __init__(self, mat):\n",
    "        self.mat = mat\n",
    "        # 二维前缀和\n",
    "        m, n = len(mat), len(mat[0])\n",
    "        self.pre = [[0] * (n + 1) for _ in range(m + 1)]\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                self.pre[i + 1][j + 1] = self.pre[i][j + 1] + \\\n",
    "                    self.pre[i + 1][j] - self.pre[i][j] + mat[i][j]\n",
    "\n",
    "    def query(self, xa, ya, xb, yb):\n",
    "        # 二维子矩阵和查询，索引从 0 开始，左上角 [xa, ya] 右下角 [xb, yb]\n",
    "        return self.pre[xb + 1][yb + 1] - self.pre[xb +\n",
    "                                                   1][ya] - self.pre[xa][yb + 1] + self.pre[xa][ya]\n",
    "\n",
    "class Solution:\n",
    "    def largest1BorderedSquare(self, grid: List[List[int]]) -> int:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        ans = 0\n",
    "        pre = PreFixSumMatrix(grid)\n",
    "        if pre.query(0, 0, m-1, n-1) == 0:\n",
    "            return 0\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                for x in range(ans+1, n+1):\n",
    "                    if i+x-1>=m or j+x-1>=n:\n",
    "                        break\n",
    "                    lst = [[i, j, i, j+x-1], [i, j, i+x-1, j], [i, j+x-1, i+x-1, j+x-1], [i+x-1, j, i+x-1, j+x-1]]\n",
    "                    if all(pre.query(a, b, c, d) ==x for a, b, c, d in lst):\n",
    "                        ans = x\n",
    "        return ans*ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "\n",
    "class PreSum:\n",
    "    def __init__(self, grid: List[List[int]]):\n",
    "        self.grid = grid\n",
    "        n, m = len(grid), len(grid[0])\n",
    "        pre_sum = [[0] * (m + 1) for _ in range(n + 1)]\n",
    "        for x in range(1, n + 1):\n",
    "            for y in range(1, m + 1):\n",
    "                pre_sum[x][y] = pre_sum[x - 1][y] \\\n",
    "                                + pre_sum[x][y - 1] \\\n",
    "                                - pre_sum[x - 1][y - 1] \\\n",
    "                                + grid[x - 1][y - 1]\n",
    "        self.pre_sum = pre_sum\n",
    "\n",
    "    def get_sum(self, ul, lr) -> int:\n",
    "        ul_x, ul_y = ul\n",
    "        lr_x, lr_y = lr\n",
    "        if not (ul_x <= lr_x and ul_y <= lr_y):\n",
    "            return 0\n",
    "        pre_sum = self.pre_sum\n",
    "        return pre_sum[lr_x + 1][lr_y + 1] \\\n",
    "            - pre_sum[ul_x][lr_y + 1] \\\n",
    "            - pre_sum[lr_x + 1][ul_y] \\\n",
    "            + pre_sum[ul_x][ul_y]\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def largest1BorderedSquare(self, grid: List[List[int]]) -> int:\n",
    "        n, m = len(grid), len(grid[0])\n",
    "        pre_sum = PreSum(grid)\n",
    "        ans_edge = 0\n",
    "        for ul_x in range(n):\n",
    "            for ul_y in range(m):\n",
    "                max_edge = min(n - ul_x, m - ul_y)\n",
    "                for edge in range(max_edge, 0, -1):\n",
    "                    flag = False\n",
    "                    if edge == 1:\n",
    "                        flag = (grid[ul_x][ul_y] == 1)\n",
    "                    else:\n",
    "                        lr_x, lr_y = ul_x + edge - 1, ul_y + edge - 1\n",
    "                        s1 = pre_sum.get_sum((ul_x, ul_y), (lr_x, lr_y))\n",
    "                        s2 = pre_sum.get_sum((ul_x + 1, ul_y + 1), (lr_x - 1, lr_y - 1))\n",
    "                        flag = (s1 - s2 == edge * 4 - 4)\n",
    "                    if flag:\n",
    "                        ans_edge = max(ans_edge, edge)\n",
    "                        break\n",
    "        return ans_edge ** 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largest1BorderedSquare(self, grid: List[List[int]]) -> int:\n",
    "        rows, cols = len(grid), len(grid[0])\n",
    "\n",
    "        right = [[0 for j in range(cols)] for i in range(rows)]\n",
    "        down  = [[0 for j in range(cols)] for i in range(rows)]\n",
    "        up    = [[0 for j in range(cols)] for i in range(rows)]\n",
    "        left  = [[0 for j in range(cols)] for i in range(rows)]\n",
    "\n",
    "        for i in range(rows):\n",
    "            left[i][0] = grid[i][0]\n",
    "            for j in range(1, cols):\n",
    "                if grid[i][j]==0:\n",
    "                    left[i][j]=0\n",
    "                else:\n",
    "                    left[i][j] = left[i][j-1] + 1\n",
    "\n",
    "        for i in range(rows):\n",
    "            right[i][-1] = grid[i][-1]\n",
    "            for j in range(cols-2, -1, -1):\n",
    "                if grid[i][j]==0:\n",
    "                    right[i][j]=0\n",
    "                else:\n",
    "                    right[i][j] = right[i][j+1] + 1 \n",
    "\n",
    "        for j in range(cols):\n",
    "            up[0][j] = grid[0][j]\n",
    "            for i in range(1, rows):\n",
    "                if grid[i][j]==0:\n",
    "                    up[i][j]=0\n",
    "                else:\n",
    "                    up[i][j] = up[i-1][j] + 1\n",
    "\n",
    "        for j in range(cols):\n",
    "            down[-1][j] = grid[-1][j]\n",
    "            for i in range(rows-2, -1, -1):\n",
    "                if grid[i][j]==0:\n",
    "                    down[i][j]=0\n",
    "                else:\n",
    "                    down[i][j] = down[i+1][j] + 1 \n",
    "\n",
    "        ans = 0\n",
    "        for i in range(rows):\n",
    "            for j in range(cols):\n",
    "                for L in range(1, min(rows, cols)+1):\n",
    "                    if right[i][j] >= L and down[i][j] >= L  and up[i+L-1][j+L-1] >= L  and left[i+L-1][j+L-1] >= L:\n",
    "                        ans = max(ans, L**2)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largest1BorderedSquare(self, grid: List[List[int]]) -> int:\n",
    "\n",
    "        n, m = len(grid), len(grid[0])\n",
    "        dp = [[0] * (m +1) for _ in range(n + 1)]\n",
    "        for i in range(1, n + 1):\n",
    "            for j in range(1, m + 1):\n",
    "                dp[i][j] = dp[i - 1][j] + dp[i][j - 1] + grid[i - 1][j - 1] - dp[i - 1][j - 1]\n",
    "        maxlen = min(n, m)\n",
    "        print(dp)\n",
    "        count = 0\n",
    "        for maxl in range(maxlen, 1, -1):\n",
    "            for r in range(maxl, n + 1):\n",
    "                for c in range(maxl, m + 1):\n",
    "\n",
    "                    if (dp[r][c] - dp[r - maxl][c] - dp[r][c - 1] + dp[r - maxl][c- 1]) == (dp[r][c] - dp[r][c - maxl] - dp[r-1][c] + dp[r - 1][c - maxl]) == (dp[r - maxl + 1][c] - dp[r - maxl + 1][c - maxl] - dp[r - maxl][c] + dp[r - maxl][c - maxl]) == (dp[r][c - maxl + 1] - dp[r][c - maxl] - dp[r - maxl][c - maxl + 1] + dp[r - maxl][c - maxl]) == maxl:\n",
    "                        return maxl * maxl\n",
    "        if dp[-1][-1]:\n",
    "            return 1\n",
    "        return 0\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "\n",
    "class PreSum:\n",
    "    def __init__(self, grid: List[List[int]]):\n",
    "        self.grid = grid\n",
    "        n, m = len(grid), len(grid[0])\n",
    "        pre_sum = [[0] * (m + 1) for _ in range(n + 1)]\n",
    "        for x in range(1, n + 1):\n",
    "            for y in range(1, m + 1):\n",
    "                pre_sum[x][y] = pre_sum[x - 1][y] \\\n",
    "                                + pre_sum[x][y - 1] \\\n",
    "                                - pre_sum[x - 1][y - 1] \\\n",
    "                                + grid[x - 1][y - 1]\n",
    "        self.pre_sum = pre_sum\n",
    "\n",
    "    def get_sum(self, ul, lr) -> int:\n",
    "        ul_x, ul_y = ul\n",
    "        lr_x, lr_y = lr\n",
    "        if not (ul_x <= lr_x and ul_y <= lr_y):\n",
    "            return 0\n",
    "        pre_sum = self.pre_sum\n",
    "        return pre_sum[lr_x + 1][lr_y + 1] \\\n",
    "            - pre_sum[ul_x][lr_y + 1] \\\n",
    "            - pre_sum[lr_x + 1][ul_y] \\\n",
    "            + pre_sum[ul_x][ul_y]\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def largest1BorderedSquare(self, grid: List[List[int]]) -> int:\n",
    "        n, m = len(grid), len(grid[0])\n",
    "        pre_sum = PreSum(grid)\n",
    "        ans_edge = 0\n",
    "        for ul_x in range(n):\n",
    "            for ul_y in range(m):\n",
    "                max_edge = min(n - ul_x, m - ul_y)\n",
    "                if max_edge <= ans_edge:\n",
    "                    break\n",
    "                for edge in range(max_edge, 0, -1):\n",
    "                    flag = False\n",
    "                    if edge == 1:\n",
    "                        flag = (grid[ul_x][ul_y] == 1)\n",
    "                    else:\n",
    "                        lr_x, lr_y = ul_x + edge - 1, ul_y + edge - 1\n",
    "                        s1 = pre_sum.get_sum((ul_x, ul_y), (lr_x, lr_y))\n",
    "                        s2 = pre_sum.get_sum((ul_x + 1, ul_y + 1), (lr_x - 1, lr_y - 1))\n",
    "                        flag = (s1 - s2 == edge * 4 - 4)\n",
    "                    if flag:\n",
    "                        ans_edge = max(ans_edge, edge)\n",
    "                        break\n",
    "        return ans_edge ** 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largest1BorderedSquare(self, grid: List[List[int]]) -> int:\n",
    "        s = [[0]*(len(grid[0])+1) for _ in range(len(grid)+1)]\n",
    "        for i in range(1, len(s)):\n",
    "            for j in range(1, len(s[0])):\n",
    "                s[i][j] = s[i-1][j] + s[i][j-1] - s[i-1][j-1] + grid[i-1][j-1]\n",
    "        \n",
    "        if s[len(s)-1][len(s[0])-1] == 0:\n",
    "            return 0\n",
    "        maxnum = 1\n",
    "        for i in range(len(grid)):\n",
    "            for j in range(len(grid[0])):\n",
    "                maxs = min(i, j) + 1\n",
    "                for n in range(maxs, 1, -1):\n",
    "                    if self.check(s, i, j, n):\n",
    "                        maxnum = max(maxnum, n**2)\n",
    "        return maxnum\n",
    "\n",
    "    def check(self, s, i, j, n):\n",
    "        s2 = self.sumRegion(s, i-n+1, j-n+1, i, j)\n",
    "        s1 = self.sumRegion(s, i-n+2, j-n+2, i-1, j-1)\n",
    "        if s2 - s1 == 2*n + 2*(n-2):\n",
    "            return True\n",
    "        else:\n",
    "            return False\n",
    "\n",
    "    def sumRegion(self, s, row1, col1, row2, col2):\n",
    "        if col1 > col2 or row1 > row2:\n",
    "            return 0\n",
    "        return s[row2+1][col2+1] - s[row2+1][col1] - s[row1][col2+1] + s[row1][col1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largest1BorderedSquare(self, grid: List[List[int]]) -> int:\n",
    "        gr = [[0]*(len(grid[0])+1) for _ in range(len(grid)+1)]\n",
    "        for i in range(1,len(gr)):\n",
    "            for j in range(1,len(gr[0])):\n",
    "                \n",
    "                gr[i][j] =gr[i-1][j]+gr[i][j-1] -gr[i-1][j-1]+grid[i-1][j-1]\n",
    "\n",
    "        print(gr)\n",
    "        \n",
    "        def  total_one(up_left,low_right):\n",
    "\n",
    "            if up_left ==low_right:\n",
    "                return 0\n",
    "\n",
    "\n",
    "            area =gr[low_right[0]][low_right[1]] -gr[low_right[0]][up_left[1]] \\\n",
    "            -gr[up_left[0]][low_right[1]] +gr[up_left[0]][up_left[1]]\n",
    "\n",
    "            return area\n",
    "\n",
    "        # print(gr)\n",
    "        for length in range(len(grid),1,-1):\n",
    "            for start0 in range(0,len(gr)-length):\n",
    "                for start1 in range(0,len(gr[0])-length):\n",
    "                    end0 =start0+length\n",
    "                    end1 = start1+length\n",
    "\n",
    "                    outerside_a = total_one([start0,start1],[end0,end1])\n",
    "                    inside_a = total_one([start0+1,start1+1],[end0-1,end1-1])\n",
    "\n",
    "\n",
    "\n",
    "                    if outerside_a -inside_a == length *4-4:\n",
    "\n",
    "                        return length **2\n",
    "        \n",
    "        if gr[-1][-1]:\n",
    "            return 1\n",
    "        else: \n",
    "            return 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\tdef largest1BorderedSquare(self, grid: List[List[int]]) -> int:\n",
    "\t\treturn self.diagonal(grid)\n",
    "\n",
    "\t\t# def largest1BorderedSquare_original(self, grid: List[List[int]]) -> int:\n",
    "\t\t# \tm = len(grid)\n",
    "\t\t# \tn = len(grid[0])\n",
    "\n",
    "\t\t# \trow = [[0]*(n+1) for _ in range(m)] #固定行 每一行之内的前缀和\n",
    "\t\t# \tcol = [[0]*n for _ in range(m+1)] #固定列 每一列之内的前缀和\n",
    "\n",
    "\t\t# \t# 更新row\n",
    "\t\t# \tfor i in range(m):\n",
    "\t\t# \t\t\tfor j in range(n):\n",
    "\t\t# \t\t\t\t\t# i,j对应grid的坐标\n",
    "\t\t# \t\t\t\t\trow[i][j+1] = row[i][j] + grid[i][j]  #[0,j) + [j] == [0,j]/[0,j+1)\n",
    "\t\t# \t\t\t\t\tcol[i+1][j] = col[i][j] + grid[i][j]\n",
    "\t\t\t\t\t\t\t\n",
    "\t\t# \t# # 更新col\n",
    "\t\t# \t# for j in range(n):\n",
    "\t\t# \t#     for i in range(m):\n",
    "\t\t# \t#         # i,j对应grid的坐标\n",
    "\t\t# \t#         col[i+1][j] = col[i][j] + grid[i][j]\n",
    "\n",
    "\t\t# \tres = 0\n",
    "\t\t# \tfor i in range(m):\n",
    "\t\t# \t\t\tfor j in range(n):\n",
    "\t\t# \t\t\t\t\tfor d in range(0, min(i,j)+1):\n",
    "\t\t# \t\t\t\t\t\t\ttop = row[i-d][j+1] - row[i-d][j-d] # i-d, j-d -> i-d, j\n",
    "\t\t# \t\t\t\t\t\t\tbtm = row[i  ][j+1] - row[i  ][j-d] # i  , j-d -> i  , j\n",
    "\t\t# \t\t\t\t\t\t\tlft = col[i+1][j-d] - col[i-d][j-d] # i-d, j-d -> i, j-d\n",
    "\t\t# \t\t\t\t\t\t\trht = col[i+1][j  ] - col[i-d][j  ] # i-d, j   -> i, j\n",
    "\t\t# \t\t\t\t\t\t\t# print(i, j, d+1, top, btm, lft, rht)\n",
    "\t\t# \t\t\t\t\t\t\tif top == d+1 and btm == d+1 and lft == d+1 and rht == d+1:\n",
    "\t\t# \t\t\t\t\t\t\t\t\tres = max(res, d+1)\n",
    "\t\t# \treturn res ** 2\n",
    "\n",
    "\n",
    "\tdef diagonal(self, grid: List[List[int]]) -> int:\n",
    "\t\tm = len(grid)\n",
    "\t\tn = len(grid[0])\n",
    "\n",
    "\t\tN = 205\n",
    "\t\tL = [0]*(n+m)\n",
    "\t\tR = [0]*(n+m)\n",
    "\n",
    "\t\t# l[i][j] 从ij出发 向左能延伸的连续1的最大距离，b t r 同理\n",
    "\t\tl = [[0]*n for _ in range(m)]\n",
    "\t\tr = [[0]*n for _ in range(m)]\n",
    "\t\tb = [[0]*n for _ in range(m)]\n",
    "\t\tt = [[0]*n for _ in range(m)]\n",
    "\n",
    "\t\tans=0\n",
    "\t\tfor i in range(m):\n",
    "\t\t\tl[i][0] = 1 if grid[i][0] == 1 else 0\n",
    "\t\t\tfor j in range(1, n): \n",
    "\t\t\t\tl[i][j] = l[i][j-1] + 1 if grid[i][j] == 1 else 0\n",
    "\n",
    "\t\t\tr[i][n-1] = 1 if grid[i][n-1] == 1 else 0\n",
    "\t\t\tfor j in range(n-2, -1, -1):\n",
    "\t\t\t\tr[i][j] = r[i][j+1] + 1 if grid[i][j] == 1 else 0\n",
    "\n",
    "\t\tfor j in range(n):\n",
    "\t\t\tt[0][j] = 1 if grid[0][j] == 1 else 0\n",
    "\t\t\tfor i in range(1, m):\n",
    "\t\t\t\tt[i][j] = t[i-1][j] + 1 if grid[i][j] == 1 else 0\n",
    "\t\t\t\n",
    "\t\t\tb[m-1][j] = 1 if grid[m-1][j] == 1 else 0\n",
    "\t\t\tfor i in range(m-2, -1, -1):\n",
    "\t\t\t\tb[i][j] = b[i+1][j] + 1 if grid[i][j] == 1 else 0\n",
    "\n",
    "\t\tfor d in range(-max(m, n), max(m,n)+1):\n",
    "\t\t\tcur = head = tail = -1\n",
    "\t\t\tdelete = [[] for _ in range(m+n)]\n",
    "\t\t\tfor k in range(n+m):\n",
    "\t\t\t\tL[k] = R[k] = -1\n",
    "\t\t\tfor i in range(max(0,d), min(m,n+d)):\n",
    "\t\t\t\tj = i-d\n",
    "\n",
    "\t\t\t\tlen0 = min(t[i][j], l[i][j])\n",
    "\t\t\t\tlen1 = min(b[i][j], r[i][j])\n",
    "\t\t\t\t\n",
    "\t\t\t\tif len1 > 0:\n",
    "\t\t\t\t\t# i可以覆盖到未来的某人，将i加入链表，附在尾部。左上角是head 右下角靠近i的是tail （注意我们附加是将i接在tail上 并成为新的tail）\n",
    "\t\t\t\t\tif tail!=-1: R[tail]=i # 先将已有的 tail -> i 右指i\n",
    "\t\t\t\t\tL[i] = tail # tail <- i 左指向 tail\n",
    "\t\t\t\t\ttail = i    # 更新 i 为新tail\n",
    "\t\t\t\t\tif head==-1: head = i # 若head为空--链表还没初始化，初始化i\n",
    "\t\t\t\t\t# i 将来可以覆盖到 i+len1-1，当指针未来访问那里后，就可以把i移除出链表 因为 i 不可能覆盖比i+len1-1更远的节点\n",
    "\t\t\t\t\t# del[x] = {y1, y2, y3 ...} 每一个 y1 他的 len1 可以覆盖到 x\n",
    "\t\t\t\t\tdelete[i+len1-1].append(i) \n",
    "\n",
    "\t\t\t\tif cur == -1 and head != -1 and head <= i-ans:\n",
    "\t\t\t\t\t# cur还没有初始化为链表上的节点，head != -1 \n",
    "\t\t\t\t\t# (此时链表非空) head <= i-ans (链表存在潜在的点 k，可能使 k <= i-ans --- ans < i-k+1 即超过当前ans)\n",
    "\t\t\t\t\t# 如果现在没有，cur就仍是-1 但随着i的增长 这部分链表总会与新i距离超过ans 可能更新ans\n",
    "\t\t\t\t\tcur = head\n",
    "\n",
    "\t\t\t\twhile cur != -1 and R[cur] != -1 and R[cur] <= i-ans:\n",
    "\t\t\t\t\t# 如果cur已经初始化，若cur右侧存在潜在的结果 (可能找到更大的ans)，右移cur\n",
    "\t\t\t\t\tcur = R[cur]\n",
    "\n",
    "\t\t\t\twhile cur != -1 and i-cur+1 <= len0:\n",
    "\t\t\t\t\t# 此时cur已停在从近往远的 可能超越ans的least点上 如果i往左上能覆盖到他，则说明它能和i组成正方形（为什么不考虑它能覆盖到i？稍后提到）移动指针\n",
    "\t\t\t\t\tans = i - cur + 1\n",
    "\t\t\t\t\tcur = L[cur]\n",
    "\t\t\t\t\n",
    "\t\t\t\tfor p in delete[i]:\n",
    "\t\t\t\t\t# 对于所有最远能覆盖到i的点，马上i要前进，del[i] 所有的点以后覆盖不到更远了，从链表中移除他们，这样回答了上问，因为我们一直保持链表点可以覆盖到当前i，一旦覆盖不到即移除\n",
    "\t\t\t\t\tif p==cur: cur = L[p]\n",
    "\t\t\t\t\tif p==head: head = R[head]\n",
    "\t\t\t\t\tif p==tail: tail=L[tail]\n",
    "\t\t\t\t\tif L[p]!=-1: R[L[p]] = R[p]\n",
    "\t\t\t\t\tif R[p]!=-1: L[R[p]] = L[p]\n",
    "\n",
    "\t\treturn ans * ans\n",
    "\n",
    "\t\t\t\t\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largest1BorderedSquare(self, grid: List[List[int]]) -> int:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "\n",
    "        # [0, 0] [left, top]\n",
    "        left_top = [[0, 0] for _ in range(m * n)]\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] == 1:\n",
    "                    if j == 0 and i == 0:\n",
    "                        left_top[0] = [1, 1]\n",
    "                    elif j == 0:\n",
    "                        top = left_top[(i - 1) * n + j][1]\n",
    "                        left_top[i * n + j] = [1, top + 1]\n",
    "                    elif i == 0:\n",
    "                        left = left_top[j - 1][0]\n",
    "                        left_top[j] = [left + 1, 1]\n",
    "                    else:\n",
    "                        top = left_top[(i - 1) * n + j][1]\n",
    "                        left = left_top[i * n + j - 1][0]\n",
    "                        left_top[i * n + j] = [left + 1, top + 1]\n",
    "\n",
    "        right_bottom = [[0, 0] for _ in range(m * n)]\n",
    "        for i in range(m-1, -1, -1):\n",
    "            for j in range(n-1, -1, -1):\n",
    "                if grid[i][j] == 1:\n",
    "                    if i == m-1 and j == n - 1:\n",
    "                        right_bottom[i * n + j] = [1, 1]\n",
    "                    elif i == m - 1:\n",
    "                        right = right_bottom[i * n + j + 1][0]\n",
    "                        right_bottom[i * n + j] = [right+1, 1]\n",
    "                    elif j == n - 1:\n",
    "                        bottom = right_bottom[(i+1) * n][1]\n",
    "                        right_bottom[i * n + j] = [1, bottom+1]\n",
    "                    else:\n",
    "                        right = right_bottom[i * n + j + 1][0]\n",
    "                        bottom = right_bottom[(i + 1) * n + j][1]\n",
    "                        right_bottom[i * n + j] = [right + 1, bottom + 1]\n",
    "        ans = 0\n",
    "        for num, item in enumerate(right_bottom):\n",
    "            if item[0] == 0:\n",
    "                continue\n",
    "            temp = 1\n",
    "            i = num // n\n",
    "            j = num % n\n",
    "            i += 1\n",
    "            j += 1\n",
    "            ans = max(ans, 1)\n",
    "            while i < m and j < n:\n",
    "                pairs = i * n + j\n",
    "                pair_item = left_top[pairs]\n",
    "                min_value = min(item + pair_item)\n",
    "                if min_value > temp:\n",
    "                    ans = max(ans, temp + 1)\n",
    "                temp += 1\n",
    "                i += 1\n",
    "                j += 1\n",
    "        return ans ** 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largest1BorderedSquare(self, grid: List[List[int]]) -> int:\n",
    "        n, m = len(grid), len(grid[0])\n",
    "        default = [0, 0, 0, 0]\n",
    "        dist_dict = dict()\n",
    "        for i in range(n):\n",
    "            for j in range(m):\n",
    "                if grid[i][j]:\n",
    "                    dist_dict[(i, j)] = [dist_dict.get((i-1, j), default)[0]+1, dist_dict.get((i, j-1), default)[1]+1, 0, 0]\n",
    "        for i in range(n-1, -1, -1):\n",
    "            for j in range(m-1, -1, -1):\n",
    "                if grid[i][j]:\n",
    "                    dist_dict[(i, j)][2] = dist_dict.get((i+1, j), default)[2] + 1\n",
    "                    dist_dict[(i, j)][3] = dist_dict.get((i, j+1), default)[3] + 1\n",
    "        ret = 0\n",
    "        for i in range(n):\n",
    "            for j in range(m):\n",
    "                if grid[i][j]:\n",
    "                    d = min(dist_dict[(i, j)][:2]) - 1\n",
    "                    cur = 1\n",
    "                    for k in range(d, 0, -1):\n",
    "                        i2, j2 = i - k, j - k\n",
    "                        if grid[i2][j2] and min(dist_dict[(i2, j2)][2:]) > k:\n",
    "                            cur = k + 1\n",
    "                            break\n",
    "                    if cur > ret:\n",
    "                        ret = cur\n",
    "        return ret * ret\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largest1BorderedSquare(self, grid: List[List[int]]) -> int:\n",
    "        n, m = len(grid), len(grid[0])\n",
    "        states = [[[0, 0] for j in range(m)] for i in range(n)]\n",
    "        ans = 0\n",
    "        for i in range(n):\n",
    "            for j in range(m):\n",
    "                if grid[i][j] == 1:\n",
    "                    states[i][j][0] = (states[i][j-1][0] + 1) if j > 0 else 1\n",
    "                    states[i][j][1] = (states[i-1][j][1] + 1) if i > 0 else 1\n",
    "\n",
    "                    min_edge = min(states[i][j])\n",
    "                    while min_edge > ans:\n",
    "                        if states[i][j-min_edge + 1][1] >= min_edge and states[i-min_edge+1][j][0] >= min_edge:\n",
    "                            ans = min_edge\n",
    "                        min_edge -= 1\n",
    "\n",
    "\n",
    "        return ans * ans \n",
    "\n",
    "\n",
    "                    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largest1BorderedSquare(self, grid: List[List[int]]) -> int:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "\n",
    "        # [0, 0] [left, top]\n",
    "        left_top = [[0, 0] for _ in range(m * n)]\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] == 1:\n",
    "                    if j == 0 and i == 0:\n",
    "                        left_top[0] = [1, 1]\n",
    "                    elif j == 0:\n",
    "                        top = left_top[(i - 1) * n + j][1]\n",
    "                        left_top[i * n + j] = [1, top + 1]\n",
    "                    elif i == 0:\n",
    "                        left = left_top[j - 1][0]\n",
    "                        left_top[j] = [left + 1, 1]\n",
    "                    else:\n",
    "                        top = left_top[(i - 1) * n + j][1]\n",
    "                        left = left_top[i * n + j - 1][0]\n",
    "                        left_top[i * n + j] = [left + 1, top + 1]\n",
    "\n",
    "        right_bottom = [[0, 0] for _ in range(m * n)]\n",
    "        for i in range(m-1, -1, -1):\n",
    "            for j in range(n-1, -1, -1):\n",
    "                if grid[i][j] == 1:\n",
    "                    if i == m-1 and j == n - 1:\n",
    "                        right_bottom[i * n + j] = [1, 1]\n",
    "                    elif i == m - 1:\n",
    "                        right = right_bottom[i * n + j + 1][0]\n",
    "                        right_bottom[i * n + j] = [right+1, 1]\n",
    "                    elif j == n - 1:\n",
    "                        bottom = right_bottom[(i+1) * n][1]\n",
    "                        right_bottom[i * n + j] = [1, bottom+1]\n",
    "                    else:\n",
    "                        right = right_bottom[i * n + j + 1][0]\n",
    "                        bottom = right_bottom[(i + 1) * n + j][1]\n",
    "                        right_bottom[i * n + j] = [right + 1, bottom + 1]\n",
    "        ans = 0\n",
    "        for num, item in enumerate(right_bottom):\n",
    "            if item[0] == 0:\n",
    "                continue\n",
    "            temp = 1\n",
    "            i = num // n\n",
    "            j = num % n\n",
    "            i += 1\n",
    "            j += 1\n",
    "            ans = max(ans, 1)\n",
    "            while i < m and j < n:\n",
    "                pairs = i * n + j\n",
    "                pair_item = left_top[pairs]\n",
    "                min_value = min(item + pair_item)\n",
    "                if min_value > temp:\n",
    "                    ans = max(ans, temp + 1)\n",
    "                temp += 1\n",
    "                i += 1\n",
    "                j += 1\n",
    "        return ans ** 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largest1BorderedSquare(self, grid: List[List[int]]) -> int:\n",
    "        n = len(grid)\n",
    "        m = len(grid[0])\n",
    "        grid.insert(0,[0]*(m+2))\n",
    "        grid.append([0]*(m+2))\n",
    "        for i in range(1,n+1):\n",
    "            grid[i].insert(0,0)\n",
    "            grid[i].append(0)\n",
    "        n +=2\n",
    "        m +=2\n",
    "        ans = 0\n",
    "        dp = [[[0,0,0,0] for _ in range(m)] for _ in range(n)]\n",
    "        for i in range(1,n-1):\n",
    "            for j in range(1,m-1):\n",
    "                if grid[i][j] != 0:\n",
    "                    dp[i][j][0] = dp[i][j-1][0]+1\n",
    "                    dp[i][j][1] = dp[i-1][j][1]+1\n",
    "                if grid[n-i-1][m-j-1] != 0:\n",
    "                    dp[n-i-1][m-j-1][2] = dp[n-i-1][m-j][2]+1\n",
    "                    dp[n-i-1][m-j-1][3] = dp[n-i][m-j-1][3]+1\n",
    "\n",
    "        for i in range(1,n-1):\n",
    "            for j in range(1,m-1):\n",
    "                if grid[i][j] !=0:\n",
    "                    border = min(dp[i][j][:2])\n",
    "                    while border>ans:\n",
    "                        if min(dp[i-border+1][j-border+1][2:])>=border:\n",
    "                            ans = border\n",
    "                            break\n",
    "                        border-=1\n",
    "\n",
    "        return ans**2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largest1BorderedSquare(self, grid: List[List[int]]) -> int:\n",
    "        # Trial\n",
    "        def get_edges(row_id, row) -> List[List[List[int]]]:\n",
    "            res = []\n",
    "            p1 = p2 = 0\n",
    "            while p1 < len(row):\n",
    "                if row[p1] == 0:\n",
    "                    p1 += 1\n",
    "                    continue\n",
    "                p2 = p1\n",
    "                while p2 < len(row) - 1 and row[p2 + 1] == 1:\n",
    "                    p2 += 1\n",
    "                for w1 in range(p1, p2):\n",
    "                    for w2 in range(w1+1, p2+1):\n",
    "                        res.append([[row_id, w1], [row_id, w2]])\n",
    "                p1 = p2 + 1\n",
    "            return res\n",
    "\n",
    "        def check_square(top_left, top_right) -> bool:\n",
    "            length = top_right[1] - top_left[1] + 1\n",
    "            top_row = top_left[0]\n",
    "            # Left and right edges\n",
    "            for r in range(top_row + 1, top_row + length):\n",
    "                try:\n",
    "                    assert grid[r][top_left[1]] == 1 and grid[r][top_right[1]] == 1\n",
    "                except:\n",
    "                    return False\n",
    "            # Bottom\n",
    "            for c in range(top_left[1], top_right[1] + 1):\n",
    "                try:\n",
    "                    assert grid[top_row + length - 1][c] == 1\n",
    "                except:\n",
    "                    return False\n",
    "            return True\n",
    "\n",
    "        res = 1 if any(n == 1 for row in grid for n in row) else 0\n",
    "        for i, row in enumerate(grid):\n",
    "            for edge in (edge for edge in get_edges(i, row) if (edge[1][1] - edge[0][1] + 1) ** 2 > res):\n",
    "                res = (edge[1][1] - edge[0][1] + 1) ** 2 if check_square(*edge) else res\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largest1BorderedSquare(self, grid: List[List[int]]) -> int:\n",
    "        xlim = len(grid)\n",
    "        ylim = len(grid[0])\n",
    "        ok = [[[0, 0] for _ in range(ylim)] for _ in range(xlim)]\n",
    "\n",
    "        for x in range(xlim):\n",
    "            ok[x][ylim-1][0] = grid[x][ylim-1]\n",
    "\n",
    "        for x in range(xlim):\n",
    "            for y in range(ylim-2, -1, -1):\n",
    "                ok[x][y][0] = grid[x][y] * (ok[x][y+1][0] + 1)\n",
    "\n",
    "        for y in range(ylim):\n",
    "            ok[xlim-1][y][1] = grid[xlim-1][y]\n",
    "        \n",
    "        for y in range(ylim):\n",
    "            for x in range(xlim-2, -1, -1):\n",
    "                ok[x][y][1] = grid[x][y] * (ok[x+1][y][1] + 1)\n",
    "\n",
    "        ans = 0\n",
    "        for x in range(xlim):\n",
    "            for y in range(ylim):\n",
    "                for l in range(ans+1, min(xlim-x, ylim-y)+1):\n",
    "                    # print(x+l-1, y+l-1)\n",
    "                    if ok[x][y][0] >= l and ok[x][y][1] >= l and ok[x+l-1][y][0] >= l and ok[x][y+l-1][1] >= l:\n",
    "                        ans = l\n",
    "\n",
    "        return ans ** 2\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largest1BorderedSquare(self, grid: List[List[int]]) -> int:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        res = 0\n",
    "        dp = [[0] * n for _ in range(m)] # m * n * 2 [left, up]\n",
    "        \n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                dp[i][j] = [0, 0]\n",
    "                if grid[i][j] == 1:\n",
    "\n",
    "                    cnt = 1\n",
    "                    dp[i][j][1] = 1\n",
    "                    dp[i][j][0] = (dp[i][j - 1][0] + 1) if j > 0 else 1\n",
    "                    \n",
    "                    for k in range(i - 1, -1, -1):\n",
    "                        if grid[k][j] == 1:\n",
    "                            dp[i][j][1] += 1\n",
    "                        else:\n",
    "                            break \n",
    "                    v = min(dp[i][j])\n",
    "                    for k in range(v, -1, -1):\n",
    "    \n",
    "                        if dp[i - k + 1][j][0] >= k and dp[i][j - k + 1][1] >= k:\n",
    "                            res = max(res, k)\n",
    "                            break\n",
    "                        \n",
    "\n",
    "\n",
    "        return res * res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largest1BorderedSquare(self, grid: List[List[int]]) -> int:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "\n",
    "        dp = [[[0, 0] for _ in range(n + 1) ]for _ in range(m + 1)] # up, left\n",
    "        ans = 0\n",
    "        for i in range(1, m + 1):\n",
    "            for j in range(1, n + 1):\n",
    "                if grid[i - 1][j - 1] == 1:\n",
    "                    dp[i][j][0] = dp[i - 1][j][0] + 1\n",
    "                    dp[i][j][1] = dp[i][j - 1][1] + 1\n",
    "\n",
    "                    d = min(dp[i][j][0], dp[i][j][1])\n",
    "                    while d > ans:\n",
    "                        if dp[i - d + 1][j][1] >= d and dp[i][j - d + 1][0] >= d:\n",
    "                            ans = d\n",
    "                        d -= 1\n",
    "        return ans ** 2"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
